package leetcode.editor.cn;
 
/**
 * 零钱兑换 II
 * @author qulq
 * @date 2024-07-24 21:11:21
 */
public class T518_CoinChangeIi{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T518_CoinChangeIi().new Solution();
	 }

	/**
	 * 完全背包
	 * 计算顺序：因为是求组合，所以一定要物品在外层、容量在内层
	 * 完全背包：物品顺序遍历即可
	 *
	 * 求组合：物品在外层、容量在内层。
	 *
	 * f[w] = f[w] +  f[w - Aj] | 0 <= j <= n
	 * 因为 f[1] = f[1] + f[0] 需要等于1，所以初始化f[0] = 1
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int change(int amount, int[] coins) {

		int[] dp = new int[amount + 1];
		dp[0] = 1;
		// 遍历物品
		for (int i = 0; i < coins.length; i++) {
			// 遍历背包
			for (int j = coins[i]; j <= amount; j++) {
				dp[j] += dp[j - coins[i]];
			}
		}
		return dp[amount];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}